1833E - Round Dance - CodeForces Solution

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~**
*             In the name of Allah, Most Gracious, Most Merciful             *
**~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

///#pragma GCC optimize("Ofast")
///#pragma GCC target("avx,avx2,fma")
///#pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

///#include<ext/pb_ds/assoc_container.hpp>
///#include<ext/pb_ds/tree_policy.hpp>
///using namespace __gnu_pbds;
///template<typename T> using orderset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
///template<typename T> using ordermultiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
///(X).order_of_key(value) /// return lower_bound(value)
///(*X).find_by_order(index) /// return value (0 index)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /// mt19937_64 (long long)

auto my_rand(long long l,long long r)
{
    return uniform_int_distribution<long long>(l,r)(rng);
}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> psi;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<bool> vbb;
typedef vector<string> vss;

const int N = 200001;
const int M = 32000;
const int MOD = 1000000007;
const int Mod = 998244353;
const int inf = 1234567890;
const ll INF = 1122334455667788990;

#define fast() ios_base::sync_with_stdio(false),cin.tie(NULL)
#define next(x) next_permutation(all(x))
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rev(a) reverse(all(a))
#define cnt(x,a) count(all(x),a)
#define n(x) int((x).size())
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define ub upper_bound
#define lb lower_bound
#define Unique(x) (x).erase(unique(all(x)),(x).end())
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define error cout<<-1<<nl
#define space ' '
#define nl '\n'
#define pi acos(-1)
#define eps 1e-9
#define sqr(x) (1LL*(x)*(x))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (1LL*(a/gcd(a,b))*b)
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define SUM(a) accumulate(all(a),0LL)
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define Case(x) cout<<"Case "<<x<<": "
#define strtoint(a) atoi(a.c_str())
#define dbg(x) cerr<<#x<<" is "<<x<<'\n';
#define fix(x) cout<<fixed<<setprecision(x)
#define coutv(v) for(auto it:v)cout<<it<<' ';cout<<nl;
#define cinv(v) for(auto &it:v)cin>>it;
#define time() cerr<<"Time elapsed : "<<clock()*1000.0/CLOCKS_PER_SEC<<"ms"<<'\n'

///.........Bit_Manipulation...........///
#define MSB(mask) 63-__builtin_clzll(mask)  /// 0 -> -1
#define LSB(mask) __builtin_ctzll(mask)  /// 0 -> 64
#define SETBIT(mask) __builtin_popcountll(mask)
#define CHECKBIT(mask,bit) (mask&(1LL<<bit))
#define ONBIT(mask,bit) (mask|(1LL<<bit))
#define OFFBIT(mask,bit) (mask&~(1LL<<bit))
#define CHANGEBIT(mask,bit) (mask^(1LL<<bit))

///................Graph's Move.................
///const int dx[] = {+1,-1,+0,+0}; ///Rock's Move
///const int dy[] = {+0,+0,+1,-1}; ///Rock's Move
///const int dx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's Move
///const int dy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const int dx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's Move
///const int dy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's Move
///*.....................-_-........................*///

vvii g(N);
bool vis[N];
int oc,par[N];
vii circle;
stack<int>st;

void dfs1(int u)
{
    vis[u]=1;
    for(auto i:g[u])
        if(!vis[i])
            dfs1(i);
    st.push(u);
}

void dfs(int u,int p=0)
{
    oc++;
    vis[u]=true;
    par[u]=p;
    for(auto v:g[u])
        if(!vis[v])
            dfs(v,u);
        else if(vis[v]&&v!=p)
        {
            int now=u;
            ///cout<<u<<space<<p<<space<<v<<nl;
            while(true)
            {
                circle.pb(now);
                if(now==v)
                    break;
                now=par[now];
                if(now==0)
                    break;
            }
        }
}

int main()      /** "So which of the favors of your Lord(Allah) would you deny?" **/
{
    fast();
    int tc=1,cs=0;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        int v[n+1];
        for(int i=1; i<=n; i++)
        {
            g[i].clear();
            vis[i]=false;
            par[i]=0;
        }
        for(int x=1; x<=n; x++)
        {
            int y;
            cin>>y;
            v[x]=y;
            g[x].pb(y);
            ///g[y].pb(x);
        }
        for(int i=1; i<=n; i++)
            if(!vis[i])
                dfs1(i);
        for(int i=1; i<=n; i++)
            vis[i]=false;
        int mx=0,mn=0,ok=0,c=0;
        while(st.size())
        {
            int i=st.top();
            st.pop();
            if(vis[i])
                continue;
            mx++;
            oc=0;
            circle.clear();
            dfs(i);
            if(circle.size())
            {
                if(circle.size()==oc)
                    mn++;
                else
                    ok++;
                ///coutv(circle);
            }
            else
                c=1;
        }
        cout<<mn+(ok+c+1)/2<<space<<mx<<nl;
    }
}